Search Results

Documents authored by Wagner, Dorothea

Document
DOI: 10.4230/LIPIcs.SEA.2021.18
Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications

Authors: Valentin Buchhold and Dorothea Wagner

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
Customizable contraction hierarchies are one of the most popular route planning frameworks in practice, due to their simplicity and versatility. In this work, we present a novel algorithm for finding k-nearest neighbors in customizable contraction hierarchies by systematically exploring the associated separator decomposition tree. Compared to previous bucket-based approaches, our algorithm requires much less target-dependent preprocessing effort. Moreover, we use our novel approach in two concrete applications. The first application are online k-closest point-of-interest queries, where the points of interest are only revealed at query time. We achieve query times of about 25 milliseconds on a continental road network, which is fast enough for interactive systems. The second application is travel demand generation. We show how to accelerate a recently introduced travel demand generator by a factor of more than 50 using our novel nearest-neighbor algorithm.
Cite as

Valentin Buchhold and Dorothea Wagner. Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{buchhold_et_al:LIPIcs.SEA.2021.18,
  author =	{Buchhold, Valentin and Wagner, Dorothea},
  title =	{{Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.18},
  URN =		{urn:nbn:de:0030-drops-137908},
  doi =		{10.4230/LIPIcs.SEA.2021.18},
  annote =	{Keywords: Nearest neighbors, points of interest, travel demand generation, radiation model, customizable contraction hierarchies}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.1
An Efficient Solution for One-To-Many Multi-Modal Journey Planning

Authors: Jonas Sauer, Dorothea Wagner, and Tobias Zündorf

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
We study the one-to-many journey planning problem in multi-modal transportation networks consisting of a public transit network and an additional, non-schedule-based mode of transport. Given a departure time and a single source vertex, we aim to compute optimal journeys to all vertices in a set of targets, optimizing both travel time and the number of transfers used. Solving this problem yields a crucial component in many other problems, such as efficient point-of-interest queries, computation of isochrones, or multi-modal traffic assignments. While many algorithms for multi-modal journey planning exist, none of them are applicable to one-to-many scenarios. Our solution is based on the combination of two state-of-the-art approaches: ULTRA, which enables efficient journey planning in multi-modal networks, but only for one-to-one queries, and (R)PHAST, which enables efficient one-to-many queries, but only in time-independent networks. Similarly to ULTRA, our new approach can be combined with any existing public transit algorithm that allows a search to all stops, which we demonstrate for CSA and RAPTOR. For small to moderately sized target sets, the resulting algorithms are nearly as fast as the pure public transit algorithms they are based on. For large target sets, we achieve a speedup of up to 7 compared to a naive one-to-many extension of a state-of-the-art multi-modal approach.
Cite as

Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. An Efficient Solution for One-To-Many Multi-Modal Journey Planning. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sauer_et_al:OASIcs.ATMOS.2020.1,
  author =	{Sauer, Jonas and Wagner, Dorothea and Z\"{u}ndorf, Tobias},
  title =	{{An Efficient Solution for One-To-Many Multi-Modal Journey Planning}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{1:1--1:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.1},
  URN =		{urn:nbn:de:0030-drops-131371},
  doi =		{10.4230/OASIcs.ATMOS.2020.1},
  annote =	{Keywords: Algorithm Engineering, Route Planning, Public Transit, One-to-Many}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.4
Integrating ULTRA and Trip-Based Routing

Authors: Jonas Sauer, Dorothea Wagner, and Tobias Zündorf

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
We study a bi-modal journey planning scenario consisting of a public transit network and a transfer graph representing a secondary transportation mode (e.g., walking or cycling). Given a pair of source and target locations, the objective is to find a Pareto set of journeys optimizing arrival time and the number of required transfers. For public transit networks with a restricted, transitively closed transfer graph, one of the fastest known algorithms solving this bi-criteria problem is Trip-Based Routing [Witt, 2015]. However, this algorithm cannot be trivially extended to unrestricted transfer graphs. In this work, we combine Trip-Based Routing with ULTRA [Baum et al., 2019], a preprocessing technique that allows any public transit algorithm that requires transitive transfers to handle an unrestricted transfer graph. Since both ULTRA and Trip-Based Routing precompute transfer shortcuts in a preprocessing phase, a naive combination of the two leads to a three-phase algorithm that performs redundant work and produces superfluous shortcuts. We therefore propose a new, integrated preprocessing phase that combines the advantages of both and reduces the number of computed shortcuts by up to a factor of 9 compared to a naive combination. The resulting query algorithm, ULTRA-Trip-Based is the fastest known algorithm for the considered problem setting, achieving a speedup of up to 4 compared to the fastest previously known approach, ULTRA-RAPTOR.
Cite as

Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Integrating ULTRA and Trip-Based Routing. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sauer_et_al:OASIcs.ATMOS.2020.4,
  author =	{Sauer, Jonas and Wagner, Dorothea and Z\"{u}ndorf, Tobias},
  title =	{{Integrating ULTRA and Trip-Based Routing}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{4:1--4:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.4},
  URN =		{urn:nbn:de:0030-drops-131408},
  doi =		{10.4230/OASIcs.ATMOS.2020.4},
  annote =	{Keywords: Algorithms, Journey Planning, Multi-Modal, Public Transportation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.9
Customizable Contraction Hierarchies with Turn Costs

Authors: Valentin Buchhold, Dorothea Wagner, Tim Zeitz, and Michael Zündorf

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
We incorporate turn restrictions and turn costs into the route planning algorithm customizable contraction hierarchies (CCH). There are two common ways to represent turn costs and restrictions. The edge-based model expands the network so that road segments become vertices and allowed turns become edges. The compact model keeps intersections as vertices, but associates a turn table with each vertex. Although CCH can be used as is on the edge-based model, the performance of preprocessing and customization is severely affected. While the expanded network is only three times larger, both preprocessing and customization time increase by up to an order of magnitude. In this work, we carefully engineer CCH to exploit different properties of the expanded graph. We reduce the increase in customization time from up to an order of magnitude to a factor of about 3. The increase in preprocessing time is reduced even further. Moreover, we present a CCH variant that works on the compact model, and show that it performs worse than the variant on the edge-based model. Surprisingly, the variant on the edge-based model even uses less space than the one on the compact model, although the compact model was developed to keep the space requirement low.
Cite as

Valentin Buchhold, Dorothea Wagner, Tim Zeitz, and Michael Zündorf. Customizable Contraction Hierarchies with Turn Costs. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{buchhold_et_al:OASIcs.ATMOS.2020.9,
  author =	{Buchhold, Valentin and Wagner, Dorothea and Zeitz, Tim and Z\"{u}ndorf, Michael},
  title =	{{Customizable Contraction Hierarchies with Turn Costs}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{9:1--9:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.9},
  URN =		{urn:nbn:de:0030-drops-131453},
  doi =		{10.4230/OASIcs.ATMOS.2020.9},
  annote =	{Keywords: Turn costs, realistic road networks, customizable contraction hierarchies, route planning, shortest paths}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.81
Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks

Authors: Ben Strasser, Dorothea Wagner, and Tim Zeitz

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We study the problem of computing shortest paths in massive road networks with traffic predictions. Incorporating traffic predictions into routing allows, for example, to avoid commuter traffic congestions. Existing techniques follow a two-phase approach: In a preprocessing step, an index is built. The index depends on the road network and the traffic patterns but not on the path start and end. The latter are the input of the query phase, in which shortest paths are computed. All existing techniques have either large index size, slow query running times, or may compute suboptimal paths. In this work, we introduce CATCHUp (Customizable Approximated Time-dependent Contraction Hierarchies through Unpacking), the first algorithm that simultaneously achieves all three objectives. The core idea of CATCHUp is to store paths instead of travel times at shortcuts. Shortcut travel times are derived lazily from the stored paths. We perform an experimental study on a set of real world instances and compare our approach with state-of-the-art techniques. Our approach achieves the fastest preprocessing, competitive query running times and up to 30 times smaller indexes than competing approaches.
Cite as

Ben Strasser, Dorothea Wagner, and Tim Zeitz. Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 81:1-81:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{strasser_et_al:LIPIcs.ESA.2020.81,
  author =	{Strasser, Ben and Wagner, Dorothea and Zeitz, Tim},
  title =	{{Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{81:1--81:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.81},
  URN =		{urn:nbn:de:0030-drops-129479},
  doi =		{10.4230/LIPIcs.ESA.2020.81},
  annote =	{Keywords: realistic road networks, time-dependent route planning, shortest paths}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.10
Engineering Exact Quasi-Threshold Editing

Authors: Lars Gottesbüren, Michael Hamann, Philipp Schoch, Ben Strasser, Dorothea Wagner, and Sven Zühlsdorf

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
Quasi-threshold graphs are {C₄, P₄}-free graphs, i.e., they do not contain any cycle or path of four nodes as an induced subgraph. We study the {C₄, P₄}-free editing problem, which is the problem of finding a minimum number of edge insertions or deletions to transform an input graph into a quasi-threshold graph. This problem is NP-hard but fixed-parameter tractable (FPT) in the number of edits by using a branch-and-bound algorithm and admits a simple integer linear programming formulation (ILP). Both methods are also applicable to the general ℱ-free editing problem for any finite set of graphs ℱ. For the FPT algorithm, we introduce a fast heuristic for computing high-quality lower bounds and an improved branching strategy. For the ILP, we engineer several variants of row generation. We evaluate both methods for quasi-threshold editing on a large set of protein similarity graphs. For most instances, our optimizations speed up the FPT algorithm by one to three orders of magnitude. The running time of the ILP, that we solve using Gurobi, becomes only slightly faster. With all optimizations, the FPT algorithm is slightly faster than the ILP, even when listing all solutions. Additionally, we show that for almost all graphs, solutions of the previously proposed quasi-threshold editing heuristic QTM are close to optimal.
Cite as

Lars Gottesbüren, Michael Hamann, Philipp Schoch, Ben Strasser, Dorothea Wagner, and Sven Zühlsdorf. Engineering Exact Quasi-Threshold Editing. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gottesburen_et_al:LIPIcs.SEA.2020.10,
  author =	{Gottesb\"{u}ren, Lars and Hamann, Michael and Schoch, Philipp and Strasser, Ben and Wagner, Dorothea and Z\"{u}hlsdorf, Sven},
  title =	{{Engineering Exact Quasi-Threshold Editing}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.10},
  URN =		{urn:nbn:de:0030-drops-120849},
  doi =		{10.4230/LIPIcs.SEA.2020.10},
  annote =	{Keywords: Edge Editing, Integer Linear Programming, FPT algorithm, Quasi-Threshold Editing}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.11
Advanced Flow-Based Multilevel Hypergraph Partitioning

Authors: Lars Gottesbüren, Michael Hamann, Sebastian Schlag, and Dorothea Wagner

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
The balanced hypergraph partitioning problem is to partition a hypergraph into k disjoint blocks of bounded size such that the sum of the number of blocks connected by each hyperedge is minimized. We present an improvement to the flow-based refinement framework of KaHyPar-MF, the current state-of-the-art multilevel k-way hypergraph partitioning algorithm for high-quality solutions. Our improvement is based on the recently proposed HyperFlowCutter algorithm for computing bipartitions of unweighted hypergraphs by solving a sequence of incremental maximum flow problems. Since vertices and hyperedges are aggregated during the coarsening phase, refinement algorithms employed in the multilevel setting must be able to handle both weighted hyperedges and weighted vertices - even if the initial input hypergraph is unweighted. We therefore enhance HyperFlowCutter to handle weighted instances and propose a technique for computing maximum flows directly on weighted hypergraphs. We compare the performance of two configurations of our new algorithm with KaHyPar-MF and seven other partitioning algorithms on a comprehensive benchmark set with instances from application areas such as VLSI design, scientific computing, and SAT solving. Our first configuration, KaHyPar-HFC, computes slightly better solutions than KaHyPar-MF using significantly less running time. The second configuration, KaHyPar-HFC*, computes solutions of significantly better quality and is still slightly faster than KaHyPar-MF. Furthermore, in terms of solution quality, both configurations also outperform all other competing partitioners.
Cite as

Lars Gottesbüren, Michael Hamann, Sebastian Schlag, and Dorothea Wagner. Advanced Flow-Based Multilevel Hypergraph Partitioning. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gottesburen_et_al:LIPIcs.SEA.2020.11,
  author =	{Gottesb\"{u}ren, Lars and Hamann, Michael and Schlag, Sebastian and Wagner, Dorothea},
  title =	{{Advanced Flow-Based Multilevel Hypergraph Partitioning}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.11},
  URN =		{urn:nbn:de:0030-drops-120859},
  doi =		{10.4230/LIPIcs.SEA.2020.11},
  annote =	{Keywords: Hypergraph Partitioning, Maximum Flows, Refinement}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.16
Faster Multi-Modal Route Planning With Bike Sharing Using ULTRA

Authors: Jonas Sauer, Dorothea Wagner, and Tobias Zündorf

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
We study multi-modal route planning in a network comprised of schedule-based public transportation, unrestricted walking, and cycling with bikes available from bike sharing stations. So far this problem has only been considered for scenarios with at most one bike sharing operator, for which MCR is the best known algorithm [Delling et al., 2013]. However, for practical applications, algorithms should be able to distinguish between bike sharing stations of multiple competing bike sharing operators. Furthermore, MCR has recently been outperformed by ULTRA for multi-modal route planning scenarios without bike sharing [Baum et al., 2019]. In this paper, we present two approaches for modeling multi-modal transportation networks with multiple bike sharing operators: The operator-dependent model requires explicit handling of bike sharing stations within the algorithm, which we demonstrate with an adapted version of MCR. In the operator-expanded model, all relevant information is encoded within an expanded network. This allows for applying any multi-modal public transit algorithm without modification, which we show for ULTRA. We proceed by describing an additional preprocessing step called operator pruning, which can be used to accelerate both approaches. We conclude our work with an extensive experimental evaluation on the networks of London, Switzerland, and Germany. Our experiments show that the new preprocessing technique accelerates both approaches significantly, with the fastest algorithm (ULTRA-RAPTOR with operator pruning) being more than an order of magnitude faster than the basic MCR approach. Moreover, the ULTRA preprocessing step also benefits from operator pruning, as its running time is reduced by a factor of 14 to 20.
Cite as

Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Faster Multi-Modal Route Planning With Bike Sharing Using ULTRA. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sauer_et_al:LIPIcs.SEA.2020.16,
  author =	{Sauer, Jonas and Wagner, Dorothea and Z\"{u}ndorf, Tobias},
  title =	{{Faster Multi-Modal Route Planning With Bike Sharing Using ULTRA}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.16},
  URN =		{urn:nbn:de:0030-drops-120905},
  doi =		{10.4230/LIPIcs.SEA.2020.16},
  annote =	{Keywords: Algorithms, Route Planning, Bike Sharing, Public Transportation}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.25
Zipping Segment Trees

Authors: Lukas Barth and Dorothea Wagner

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
Stabbing queries in sets of intervals are usually answered using segment trees. A dynamic variant of segment trees has been presented by van Kreveld and Overmars, which uses red-black trees to do rebalancing operations. This paper presents zipping segment trees - dynamic segment trees based on zip trees, which were recently introduced by Tarjan et al. To facilitate zipping segment trees, we show how to uphold certain segment tree properties during the operations of a zip tree. We present an in-depth experimental evaluation and comparison of dynamic segment trees based on red-black trees, weight-balanced trees and several variants of the novel zipping segment trees. Our results indicate that zipping segment trees perform better than rotation-based alternatives.
Cite as

Lukas Barth and Dorothea Wagner. Zipping Segment Trees. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barth_et_al:LIPIcs.SEA.2020.25,
  author =	{Barth, Lukas and Wagner, Dorothea},
  title =	{{Zipping Segment Trees}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.25},
  URN =		{urn:nbn:de:0030-drops-120990},
  doi =		{10.4230/LIPIcs.SEA.2020.25},
  annote =	{Keywords: Segment Trees, Dynamic Segment Trees, Zip Trees, Data Structures}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.14
UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution

Authors: Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We study a multi-modal route planning scenario consisting of a public transit network and a transfer graph representing a secondary transportation mode (e.g., walking or taxis). The objective is to compute all journeys that are Pareto-optimal with respect to arrival time and the number of required transfers. While various existing algorithms can efficiently compute optimal journeys in either a pure public transit network or a pure transfer graph, combining the two increases running times significantly. As a result, even walking between stops is typically limited by a maximal duration or distance, or by requiring the transfer graph to be transitively closed. To overcome these shortcomings, we propose a novel preprocessing technique called ULTRA (UnLimited TRAnsfers): Given a complete transfer graph (without any limitations, representing an arbitrary non-schedule-based mode of transportation), we compute a small number of transfer shortcuts that are provably sufficient for computing all Pareto-optimal journeys. We demonstrate the practicality of our approach by showing that these transfer shortcuts can be integrated into a variety of state-of-the-art public transit algorithms, establishing the ULTRA-Query algorithm family. Our extensive experimental evaluation shows that ULTRA is able to improve these algorithms from limited to unlimited transfers without sacrificing query speed, yielding the fastest known algorithms for multi-modal routing. This is true not just for walking, but also for other transfer modes such as cycling or driving.
Cite as

Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{baum_et_al:LIPIcs.ESA.2019.14,
  author =	{Baum, Moritz and Buchhold, Valentin and Sauer, Jonas and Wagner, Dorothea and Z\"{u}ndorf, Tobias},
  title =	{{UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.14},
  URN =		{urn:nbn:de:0030-drops-111352},
  doi =		{10.4230/LIPIcs.ESA.2019.14},
  annote =	{Keywords: Algorithms, Optimization, Route Planning, Public Transportation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.52
Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm

Authors: Lars Gottesbüren, Michael Hamann, and Dorothea Wagner

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
In this paper, we propose HyperFlowCutter, an algorithm for balanced hypergraph bipartitioning that is based on minimum S-T hyperedge cuts and maximum flows. It computes a sequence of bipartitions that optimize cut size and balance in the Pareto sense, being able to trade one for the other. HyperFlowCutter builds on the FlowCutter algorithm for partitioning graphs. We propose additional features, such as handling disconnected hypergraphs, novel methods for obtaining starting S,T pairs as well as an approach to refine a given partition with HyperFlowCutter. Our main contribution is ReBaHFC, a new algorithm which obtains an initial partition with the fast multilevel hypergraph partitioner PaToH and then improves it using HyperFlowCutter as a refinement algorithm. ReBaHFC is able to significantly improve the solution quality of PaToH at little additional running time. The solution quality is only marginally worse than that of the best-performing hypergraph partitioners KaHyPar and hMETIS, while being one order of magnitude faster. Thus ReBaHFC offers a new time-quality trade-off in the current spectrum of hypergraph partitioners. For the special case of perfectly balanced bipartitioning, only the much slower plain HyperFlowCutter yields slightly better solutions than ReBaHFC, while only PaToH is faster than ReBaHFC.
Cite as

Lars Gottesbüren, Michael Hamann, and Dorothea Wagner. Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gottesburen_et_al:LIPIcs.ESA.2019.52,
  author =	{Gottesb\"{u}ren, Lars and Hamann, Michael and Wagner, Dorothea},
  title =	{{Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.52},
  URN =		{urn:nbn:de:0030-drops-111730},
  doi =		{10.4230/LIPIcs.ESA.2019.52},
  annote =	{Keywords: Hypergraph Partitioning, Maximum Flows, Algorithm Engineering}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.55
Engineering Negative Cycle Canceling for Wind Farm Cabling

Authors: Sascha Gritzbach, Torsten Ueckerdt, Dorothea Wagner, Franziska Wegner, and Matthias Wolf

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
In a wind farm turbines convert wind energy into electrical energy. The generation of each turbine is transmitted, possibly via other turbines, to a substation that is connected to the power grid. On every possible interconnection there can be at most one of various different cable types. Each cable type comes with a cost per unit length and with a capacity. Designing a cost-minimal cable layout for a wind farm to feed all turbine production into the power grid is called the Wind Farm Cabling Problem (WCP). We consider a formulation of WCP as a flow problem on a graph where the cost of a flow on an edge is modeled by a step function originating from the cable types. Recently, we presented a proof-of-concept for a negative cycle canceling-based algorithm for WCP [Sascha Gritzbach et al., 2018]. We extend key steps of that heuristic and build a theoretical foundation that explains how this heuristic tackles the problems arising from the special structure of WCP. A thorough experimental evaluation identifies the best setup of the algorithm and compares it to existing methods from the literature such as Mixed-integer Linear Programming (MILP) and Simulated Annealing (SA). The heuristic runs in a range of half a millisecond to under two minutes on instances with up to 500 turbines. It provides solutions of similar quality compared to both competitors with running times of one hour and one day. When comparing the solution quality after a running time of two seconds, our algorithm outperforms the MILP- and SA-approaches, which allows it to be applied in interactive wind farm planning.
Cite as

Sascha Gritzbach, Torsten Ueckerdt, Dorothea Wagner, Franziska Wegner, and Matthias Wolf. Engineering Negative Cycle Canceling for Wind Farm Cabling. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gritzbach_et_al:LIPIcs.ESA.2019.55,
  author =	{Gritzbach, Sascha and Ueckerdt, Torsten and Wagner, Dorothea and Wegner, Franziska and Wolf, Matthias},
  title =	{{Engineering Negative Cycle Canceling for Wind Farm Cabling}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{55:1--55:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.55},
  URN =		{urn:nbn:de:0030-drops-111766},
  doi =		{10.4230/LIPIcs.ESA.2019.55},
  annote =	{Keywords: Negative Cycle Canceling, Step Cost Function, Wind Farm Planning}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.11
Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades

Authors: Corrie Jacobien Carstens, Michael Hamann, Ulrich Meyer, Manuel Penschuck, Hung Tran, and Dorothea Wagner

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Graph randomisation is a crucial task in the analysis and synthesis of networks. It is typically implemented as an edge switching process (ESMC) repeatedly swapping the nodes of random edge pairs while maintaining the degrees involved [Mihail and Zegura, 2003]. Curveball is a novel approach that instead considers the whole neighbourhoods of randomly drawn node pairs. Its Markov chain converges to a uniform distribution, and experiments suggest that it requires less steps than the established ESMC [Carstens et al., 2016]. Since trades however are more expensive, we study Curveball's practical runtime by introducing the first efficient Curveball algorithms: the I/O-efficient EM-CB for simple undirected graphs and its internal memory pendant IM-CB. Further, we investigate global trades [Carstens et al., 2016] processing every node in a single super step, and show that undirected global trades converge to a uniform distribution and perform superior in practice. We then discuss EM-GCB and EM-PGCB for global trades and give experimental evidence that EM-PGCB achieves the quality of the state-of-the-art ESMC algorithm EM-ES [M. Hamann et al., 2017] nearly one order of magnitude faster.
Cite as

Corrie Jacobien Carstens, Michael Hamann, Ulrich Meyer, Manuel Penschuck, Hung Tran, and Dorothea Wagner. Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{carstens_et_al:LIPIcs.ESA.2018.11,
  author =	{Carstens, Corrie Jacobien and Hamann, Michael and Meyer, Ulrich and Penschuck, Manuel and Tran, Hung and Wagner, Dorothea},
  title =	{{Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.11},
  URN =		{urn:nbn:de:0030-drops-94745},
  doi =		{10.4230/LIPIcs.ESA.2018.11},
  annote =	{Keywords: Graph randomisation, Curveball, I/O-efficiency, Parallelism}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.27
Real-Time Traffic Assignment Using Fast Queries in Customizable Contraction Hierarchies

Authors: Valentin Buchhold, Peter Sanders, and Dorothea Wagner

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
Given an urban road network and a set of origin-destination (OD) pairs, the traffic assignment problem asks for the traffic flow on each road segment. A common solution employs a feasible-direction method, where the direction-finding step requires many shortest-path computations. In this paper, we significantly accelerate the computation of flow patterns, enabling interactive transportation and urban planning applications. We achieve this by revisiting and carefully engineering known speedup techniques for shortest paths, and combining them with customizable contraction hierarchies. In particular, our accelerated elimination tree search is more than an order of magnitude faster for local queries than the original algorithm, and our centralized search speeds up batched point-to-point shortest paths by a factor of up to 6. These optimizations are independent of traffic assignment and can be generally used for (batched) point-to-point queries. In contrast to prior work, our evaluation uses real-world data for all parts of the problem. On a metropolitan area encompassing more than 2.7 million inhabitants, we reduce the flow-pattern computation for a typical two-hour morning peak from 76.5 to 10.5 seconds on one core, and 4.3 seconds on four cores. This represents a speedup of 18 over the state of the art, and three orders of magnitude over the Dijkstra-based baseline.
Cite as

Valentin Buchhold, Peter Sanders, and Dorothea Wagner. Real-Time Traffic Assignment Using Fast Queries in Customizable Contraction Hierarchies. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{buchhold_et_al:LIPIcs.SEA.2018.27,
  author =	{Buchhold, Valentin and Sanders, Peter and Wagner, Dorothea},
  title =	{{Real-Time Traffic Assignment Using Fast Queries in Customizable Contraction Hierarchies}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.27},
  URN =		{urn:nbn:de:0030-drops-89623},
  doi =		{10.4230/LIPIcs.SEA.2018.27},
  annote =	{Keywords: traffic assignment, equilibrium flow pattern, customizable contraction hierarchies, batched shortest paths}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.4
Improved Oracles for Time-Dependent Road Networks

Authors: Spyros Kontogiannis, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, and Christos Zaroliagis

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
A novel landmark-based oracle (CFLAT) is presented, which provides earliest-arrival-time route plans in time-dependent road networks. To our knowledge, this is the first oracle that preprocesses combinatorial structures (collections of time-stamped min-travel-time-path trees) rather than travel-time functions. The preprocessed data structure is exploited by a new query algorithm (CFCA) which also computes (and pays for it) the actual connecting path that preserves the theoretical approximation guarantees. To make it practical and tackle the main burden of landmark-based oracles (the large preprocessing requirements), CFLAT is extensively engineered. A thorough experimental evaluation on two real-world benchmark instances shows that CFLAT achieves a significant improvement on preprocessing, approximation guarantees and query-times, in comparison to previous landmark-based oracles. It also achieves competitive query-time performance compared to state-of-art speedup heuristics for time-dependent road networks, whose query-times in most cases do not account for path construction.
Cite as

Spyros Kontogiannis, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, and Christos Zaroliagis. Improved Oracles for Time-Dependent Road Networks. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2017.4,
  author =	{Kontogiannis, Spyros and Papastavrou, Georgia and Paraskevopoulos, Andreas and Wagner, Dorothea and Zaroliagis, Christos},
  title =	{{Improved Oracles for Time-Dependent Road Networks}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{4:1--4:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.4},
  URN =		{urn:nbn:de:0030-drops-78954},
  doi =		{10.4230/OASIcs.ATMOS.2017.4},
  annote =	{Keywords: Time-dependent shortest paths, FIFO property, Distance oracles}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.7
Public Transit Routing with Unrestricted Walking

Authors: Dorothea Wagner and Tobias Zündorf

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
We study the problem of answering profile queries in public transportation networks that allow unrestricted walking. That is, finding all Pareto-optimal journeys regarding travel time and number of transfers in a given time interval. We introduce a novel algorithm that, unlike most state-of-the-art algorithms, can compute profiles efficiently in a setting that allows arbitrary walking. Using our algorithm, we show in an extensive experimental study that allowing unrestricted walking, significantly reduces travel times, compared to settings where walking is restricted. Beyond that, we publish the transportation networks of Switzerland that we used in our study, in order to encourage further research on this topic.
Cite as

Dorothea Wagner and Tobias Zündorf. Public Transit Routing with Unrestricted Walking. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{wagner_et_al:OASIcs.ATMOS.2017.7,
  author =	{Wagner, Dorothea and Z\"{u}ndorf, Tobias},
  title =	{{Public Transit Routing with Unrestricted Walking}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{7:1--7:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.7},
  URN =		{urn:nbn:de:0030-drops-78914},
  doi =		{10.4230/OASIcs.ATMOS.2017.7},
  annote =	{Keywords: Algorithms, Optimization, Route planning, Public transportation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.11
Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles

Authors: Moritz Baum, Julian Dibbelt, Dorothea Wagner, and Tobias Zündorf

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We study the problem of computing constrained shortest paths for battery electric vehicles. Since battery capacities are limited, fastest routes are often infeasible. Instead, users are interested in fast routes where the energy consumption does not exceed the battery capacity. For that, drivers can deliberately reduce speed to save energy. Hence, route planning should provide both path and speed recommendations. To tackle the resulting NP-hard optimization problem, previous work trades correctness or accuracy of the underlying model for practical running times. In this work, we present a novel framework to compute optimal constrained shortest paths for electric vehicles that uses more realistic physical models, while taking speed adaptation into account. Careful algorithm engineering makes the approach practical even on large, realistic road networks: We compute optimal solutions in less than a second for typical battery capacities, matching performance of previous inexact methods. For even faster performance, the approach can easily be extended with heuristics that provide high quality solutions within milliseconds.
Cite as

Moritz Baum, Julian Dibbelt, Dorothea Wagner, and Tobias Zündorf. Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{baum_et_al:LIPIcs.ESA.2017.11,
  author =	{Baum, Moritz and Dibbelt, Julian and Wagner, Dorothea and Z\"{u}ndorf, Tobias},
  title =	{{Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.11},
  URN =		{urn:nbn:de:0030-drops-78672},
  doi =		{10.4230/LIPIcs.ESA.2017.11},
  annote =	{Keywords: electric vehicles, constrained shortest paths, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.19
Consumption Profiles in Route Planning for Electric Vehicles: Theory and Applications

Authors: Moritz Baum, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
In route planning for electric vehicles (EVs), consumption profiles are a functional representation of optimal energy consumption between two locations, subject to initial state of charge. Efficient computation of profiles is a relevant problem on its own, but also a fundamental ingredient to many route planning approaches for EVs. In this work, we show that the complexity of a profile is at most linear in the graph size. Based on this insight, we derive a polynomial-time algorithm for the problem of finding an energy-optimal path between two locations that allows stops at charging stations. Exploiting efficient profile search, our approach also allows partial recharging at charging stations to save energy. In a sense, our results close the gap between efficient techniques for energy-optimal routes (based on simpler models) and NP-hard time-constrained problems involving charging stops for EVs. We propose a practical implementation, which we carefully integrate with Contraction Hierarchies and A* search. Even though the practical variant formally drops correctness, a comprehensive experimental study on a realistic, large-scale road network reveals that it always finds the optimal solution in our tests and computes even long-distance routes with charging stops in less than 300 ms.
Cite as

Moritz Baum, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Consumption Profiles in Route Planning for Electric Vehicles: Theory and Applications. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{baum_et_al:LIPIcs.SEA.2017.19,
  author =	{Baum, Moritz and Sauer, Jonas and Wagner, Dorothea and Z\"{u}ndorf, Tobias},
  title =	{{Consumption Profiles in Route Planning for Electric Vehicles: Theory and Applications}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.19},
  URN =		{urn:nbn:de:0030-drops-76088},
  doi =		{10.4230/LIPIcs.SEA.2017.19},
  annote =	{Keywords: electric vehicles, charging station, shortest paths, route planning, profile search, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.20
Efficient Traffic Assignment for Public Transit Networks

Authors: Lars Briem, Sebastian Buck, Holger Ebhart, Nicolai Mallig, Ben Strasser, Peter Vortisch, Dorothea Wagner, and Tobias Zündorf

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
We study the problem of computing traffic assignments for public transit networks: Given a public transit network and a demand (i.e. a list of passengers, each with associated origin, destination, and departure time), the objective is to compute the utilization of every vehicle. Efficient assignment algorithms are a core component of many urban traffic planning tools. In this work, we present a novel algorithm for computing public transit assignments. Our approach is based upon a microscopic Monte Carlo simulation of individual passengers. In order to model realistic passenger behavior, we base all routing decisions on travel time, number of transfers, time spent walking or waiting, and delay robustness. We show how several passengers can be processed during a single scan of the network, based on the Connection Scan Algorithm [Dibbelt et al., LNCS Springer 2013], resulting in a highly efficient algorithm. We conclude with an experimental study, showing that our assignments are comparable in terms of quality to the state-of-the-art. Using the parallelized version of our algorithm, we are able to compute a traffic assignment for more than ten million passengers in well below a minute, which outperforms previous works by more than an order of magnitude.
Cite as

Lars Briem, Sebastian Buck, Holger Ebhart, Nicolai Mallig, Ben Strasser, Peter Vortisch, Dorothea Wagner, and Tobias Zündorf. Efficient Traffic Assignment for Public Transit Networks. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{briem_et_al:LIPIcs.SEA.2017.20,
  author =	{Briem, Lars and Buck, Sebastian and Ebhart, Holger and Mallig, Nicolai and Strasser, Ben and Vortisch, Peter and Wagner, Dorothea and Z\"{u}ndorf, Tobias},
  title =	{{Efficient Traffic Assignment for Public Transit Networks}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.20},
  URN =		{urn:nbn:de:0030-drops-76109},
  doi =		{10.4230/LIPIcs.SEA.2017.20},
  annote =	{Keywords: Algorithms, Optimization, Route planning, Public transportation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.47
Hierarchical Time-Dependent Oracles

Authors: Spyros Kontogiannis, Dorothea Wagner, and Christos Zaroliagis

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We study networks obeying time-dependent min-cost path metrics, and present novel oracles for them which provably achieve two unique features: (i) subquadratic preprocessing time and space, independent of the metric’s amount of disconcavity; (ii) sublinear query time, in either the network size or the actual Dijkstra-Rank of the query at hand.
Cite as

Spyros Kontogiannis, Dorothea Wagner, and Christos Zaroliagis. Hierarchical Time-Dependent Oracles. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:LIPIcs.ISAAC.2016.47,
  author =	{Kontogiannis, Spyros and Wagner, Dorothea and Zaroliagis, Christos},
  title =	{{Hierarchical Time-Dependent Oracles}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.47},
  URN =		{urn:nbn:de:0030-drops-68170},
  doi =		{10.4230/LIPIcs.ISAAC.2016.47},
  annote =	{Keywords: Time-dependent shortest paths, FIFO property, Distance oracles}
}
Document
DOI: 10.4230/DagRep.6.4.139
Algorithmic Methods for Optimization in Public Transport (Dagstuhl Seminar 16171)

Authors: Leo G. Kroon, Anita Schöbel, and Dorothea Wagner

Published in: Dagstuhl Reports, Volume 6, Issue 4 (2016)

Abstract
This report documents the talks and discussions at the Dagstuhl seminar 16171 “Algorithmic Methods for Optimization in Public Transport”. The seminar brought together researchers from algorithm, algorithm engineering, operations research, mathematical optimization and engineering, all interested in algorithms in public transportation. Also several practitioners were able to join the group and brought valuable insights on current practice and challenging problems.
Cite as

Leo G. Kroon, Anita Schöbel, and Dorothea Wagner. Algorithmic Methods for Optimization in Public Transport (Dagstuhl Seminar 16171). In Dagstuhl Reports, Volume 6, Issue 4, pp. 139-160, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{kroon_et_al:DagRep.6.4.139,
  author =	{Kroon, Leo G. and Sch\"{o}bel, Anita and Wagner, Dorothea},
  title =	{{Algorithmic Methods for Optimization in Public Transport (Dagstuhl Seminar 16171)}},
  pages =	{139--160},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{4},
  editor =	{Kroon, Leo G. and Sch\"{o}bel, Anita and Wagner, Dorothea},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.4.139},
  URN =		{urn:nbn:de:0030-drops-66949},
  doi =		{10.4230/DagRep.6.4.139},
  annote =	{Keywords: delay and disruption management, dynamic passenger information, public transportation, resource scheduling, timetabling}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2015.1
Towards Realistic Pedestrian Route Planning

Authors: Simeon Andreev, Julian Dibbelt, Martin Nöllenburg, Thomas Pajor, and Dorothea Wagner

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

Abstract
Pedestrian routing has its specific set of challenges, which are often neglected by state-of-the-art route planners. For instance, the lack of detailed sidewalk data and the inability to traverse plazas and parks in a natural way often leads to unappealing and suboptimal routes. In this work, we first propose to augment the network by generating sidewalks based on the street geometry and adding edges for routing over plazas and squares. Using this and further information, our query algorithm seamlessly handles node-to-node queries and queries whose origin or destination is an arbitrary location on a plaza or inside a park. Our experiments show that we are able to compute appealing pedestrian routes at negligible overhead over standard routing algorithms.
Cite as

Simeon Andreev, Julian Dibbelt, Martin Nöllenburg, Thomas Pajor, and Dorothea Wagner. Towards Realistic Pedestrian Route Planning. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{andreev_et_al:OASIcs.ATMOS.2015.1,
  author =	{Andreev, Simeon and Dibbelt, Julian and N\"{o}llenburg, Martin and Pajor, Thomas and Wagner, Dorothea},
  title =	{{Towards Realistic Pedestrian Route Planning}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{1--15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.1},
  URN =		{urn:nbn:de:0030-drops-54592},
  doi =		{10.4230/OASIcs.ATMOS.2015.1},
  annote =	{Keywords: pedestrian routing, realistic model, shortest paths, speed-up technique}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.1
Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time

Authors: Julian Dibbelt, Ben Strasser, and Dorothea Wagner

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
We study the problem of computing delay-robust routes in timetable networks. Instead of a single path we compute a decision graph containing all stops and trains/vehicles that might be relevant. Delays are formalized using a stochastic model. We show how to compute a decision graph that minimizes the expected arrival time while bounding the latest arrival time over all sub-paths. Finally we show how the information contained within a decision graph can compactly be represented to the user. We experimentally evaluate our algorithms and show that the running times allow for interactive usage on a realistic train network.
Cite as

Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{dibbelt_et_al:OASIcs.ATMOS.2014.1,
  author =	{Dibbelt, Julian and Strasser, Ben and Wagner, Dorothea},
  title =	{{Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{1--14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.1},
  URN =		{urn:nbn:de:0030-drops-47488},
  doi =		{10.4230/OASIcs.ATMOS.2014.1},
  annote =	{Keywords: Algorithms, Optimization, Delay-robustness, Route planning, Public transportation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.138
Speed-Consumption Tradeoff for Electric Vehicle Route Planning

Authors: Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor, and Dorothea Wagner

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
We study the problem of computing routes for electric vehicles (EVs) in road networks. Since their battery capacity is limited, and consumed energy per distance increases with velocity, driving the fastest route is often not desirable and may even be infeasible. On the other hand, the energy-optimal route may be too conservative in that it contains unnecessary detours or simply takes too long. In this work, we propose to use multicriteria optimization to obtain Pareto sets of routes that trade energy consumption for speed. In particular, we exploit the fact that the same road segment can be driven at different speeds within reasonable intervals. As a result, we are able to provide routes with low energy consumption that still follow major roads, such as freeways. Unfortunately, the size of the resulting Pareto sets can be too large to be practical. We therefore also propose several nontrivial techniques that can be applied on-line at query time in order to speed up computation and filter insignificant solutions from the Pareto sets. Our extensive experimental study, which uses a real-world energy consumption model, reveals that we are able to compute diverse sets of alternative routes on continental networks that closely resemble the exact Pareto set in just under a second---several orders of magnitude faster than the exhaustive algorithm.
Cite as

Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor, and Dorothea Wagner. Speed-Consumption Tradeoff for Electric Vehicle Route Planning. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 138-151, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{baum_et_al:OASIcs.ATMOS.2014.138,
  author =	{Baum, Moritz and Dibbelt, Julian and H\"{u}bschle-Schneider, Lorenz and Pajor, Thomas and Wagner, Dorothea},
  title =	{{Speed-Consumption Tradeoff for Electric Vehicle Route Planning}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{138--151},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.138},
  URN =		{urn:nbn:de:0030-drops-47583},
  doi =		{10.4230/OASIcs.ATMOS.2014.138},
  annote =	{Keywords: electric vehicles, shortest paths, route planning, bicriteria optimization, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.226
Online Dynamic Power Management with Hard Real-Time Guarantees

Authors: Jian-Jia Chen, Mong-Jen Kao, D.T. Lee, Ignaz Rutter, and Dorothea Wagner

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We consider the problem of online dynamic power management that provides hard real-time guarantees for multi-processor systems. In this problem, a set of jobs, each associated with an arrival time, a deadline, and an execution time, arrives to the system in an online fashion. The objective is to compute a non-migrative preemptive schedule of the jobs and a sequence of power on/off operations of the processors so as to minimize the total energy consumption while ensuring that all the deadlines of the jobs are met. We assume that we can use as many processors as necessary. In this paper we examine the complexity of this problem and provide online strategies that lead to practical energy-efficient solutions for real-time multi-processor systems. First, we consider the case for which we know in advance that the set of jobs can be scheduled feasibly on a single processor. We show that, even in this case, the competitive factor of any online algorithm is at least 2.06. On the other hand, we give a 4-competitive online algorithm that uses at most two processors. For jobs with unit execution times, the competitive factor of this algorithm improves to 3.59. Second, we relax our assumption by considering as input multiple streams of jobs, each of which can be scheduled feasibly on a single processor. We present a trade-off between the energy-efficiency of the schedule and the number of processors to be used. More specifically, for k given job streams and h processors with h>k, we give a scheduling strategy such that the energy usage is at most 4.k/(h-k) times that used by any schedule which schedules each of the k streams on a separate processor. Finally, we drop the assumptions on the input set of jobs. We show that the competitive factor of any online algorithm is at least 2.28, even for the case of unit job execution times for which we further derive an O(1)-competitive algorithm.
Cite as

Jian-Jia Chen, Mong-Jen Kao, D.T. Lee, Ignaz Rutter, and Dorothea Wagner. Online Dynamic Power Management with Hard Real-Time Guarantees. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 226-238, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.STACS.2014.226,
  author =	{Chen, Jian-Jia and Kao, Mong-Jen and Lee, D.T. and Rutter, Ignaz and Wagner, Dorothea},
  title =	{{Online Dynamic Power Management with Hard Real-Time Guarantees}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{226--238},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.226},
  URN =		{urn:nbn:de:0030-drops-44607},
  doi =		{10.4230/LIPIcs.STACS.2014.226},
  annote =	{Keywords: Energy-Efficient Scheduling, Online Dynamic Power Management}
}
Document
DOI: 10.4230/DagRep.3.9.169
Algorithm Engineering (Dagstuhl Seminar 13391)

Authors: Andrew V. Goldberg, Giuseppe F. Italiano, David S. Johnson, and Dorothea Wagner

Published in: Dagstuhl Reports, Volume 3, Issue 9 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13391 "Algorithm Engineering". The algorithm engineering approach consists of a cycle of algorithm design, analysis, implementation, and experimental evaluation, with the aim of bridging the gap between theory and practice in the area of algorithms. This cycle of phases is driven by falsifiable hypotheses validated by experiments. Moreover, real-world instances often have direct impact on this cycle since they often expose modeling and analysis shortcomings. Algorithm engineering touches other research areas such as algorithm theory, combinatorial optimization, computer architecture, parallel and distributed computing, high-performance computing, and operations research. Prominent success stories in algorithm engineering include the linear program solver CPLEX, the traveling salesman suite CONCORDE, speed-up techniques for shortest paths computation, for example, in route planning, as well as graph partitioning and the computation of Steiner trees. All these topics are driven by the need for efficient algorithms and libraries for problems that appear frequently in real-world applications. In the last fifteen years, this approach to algorithmic research has gained increasing attention. There is an ACM Journal on Experimental Algorithmics and several annual conferences (WAE/ESA applied track since 1997, Alenex since 1998, and WEA/SEA since 2001) and the series of DIMACS implementation challenges where people meet to compare implementations for a specific problem. From 2007 to 2013 the German Research Foundation also funded a special priority program on algorithm engineering (DFG SPP 1307).
Cite as

Andrew V. Goldberg, Giuseppe F. Italiano, David S. Johnson, and Dorothea Wagner. Algorithm Engineering (Dagstuhl Seminar 13391). In Dagstuhl Reports, Volume 3, Issue 9, pp. 169-189, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{goldberg_et_al:DagRep.3.9.169,
  author =	{Goldberg, Andrew V. and Italiano, Giuseppe F. and Johnson, David S. and Wagner, Dorothea},
  title =	{{Algorithm Engineering (Dagstuhl Seminar 13391)}},
  pages =	{169--189},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{3},
  number =	{9},
  editor =	{Goldberg, Andrew V. and Italiano, Giuseppe F. and Johnson, David S. and Wagner, Dorothea},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.9.169},
  URN =		{urn:nbn:de:0030-drops-44214},
  doi =		{10.4230/DagRep.3.9.169},
  annote =	{Keywords: Algorithm Engineering, Science of Algorithmics, Manycore Algorithms, Certifying Algorithms, Web Search, Large Graphs}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.71
On the Complexity of Partitioning Graphs for Arc-Flags

Authors: Reinhard Bauer, Moritz Baum, Ignaz Rutter, and Dorothea Wagner

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
Precomputation of auxiliary data in an additional off-line step is a common approach towards improving the performance of shortest-path queries in large-scale networks. One such technique is the arc-flags algorithm, where the preprocessing involves computing a partition of the input graph. The quality of this partition significantly affects the speed-up observed in the query phase. It is evaluated by considering the search-space size of subsequent shortest-path queries, in particular its maximum or its average over all queries. In this paper, we substantially strengthen existing hardness results of Bauer et al. and show that optimally filling this degree of freedom is NP-hard for trees with unit-length edges, even if we bound the height or the degree. On the other hand, we show that optimal partitions for paths can be computed efficiently and give approximation algorithms for cycles and trees.
Cite as

Reinhard Bauer, Moritz Baum, Ignaz Rutter, and Dorothea Wagner. On the Complexity of Partitioning Graphs for Arc-Flags. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 71-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:OASIcs.ATMOS.2012.71,
  author =	{Bauer, Reinhard and Baum, Moritz and Rutter, Ignaz and Wagner, Dorothea},
  title =	{{On the Complexity of Partitioning Graphs for Arc-Flags}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{71--82},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.71},
  URN =		{urn:nbn:de:0030-drops-37048},
  doi =		{10.4230/OASIcs.ATMOS.2012.71},
  annote =	{Keywords: shortest paths, arc-flags, search space, preprocessing, complexity}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2009.2145
Efficient Route Planning in Flight Networks

Authors: Daniel Delling, Thomas Pajor, Dorothea Wagner, and Christos Zaroliagis

Published in: OASIcs, Volume 12, 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (2009)

Abstract
We present a set of three new time-dependent models with increasing flexibility for realistic route planning in flight networks. By these means, we obtain small graph sizes while modeling airport procedures in a realistic way. With these graphs, we are able to efficiently compute a set of best connections with multiple criteria over a full day. It even turns out that due to the very limited graph sizes it is feasible to precompute full distance tables between all airports. As a result, best connections can be retrieved in a few microseconds on real world data.
Cite as

Daniel Delling, Thomas Pajor, Dorothea Wagner, and Christos Zaroliagis. Efficient Route Planning in Flight Networks. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{delling_et_al:OASIcs.ATMOS.2009.2145,
  author =	{Delling, Daniel and Pajor, Thomas and Wagner, Dorothea and Zaroliagis, Christos},
  title =	{{Efficient Route Planning in Flight Networks}},
  booktitle =	{9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
  pages =	{1--17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-11-8},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{12},
  editor =	{Clausen, Jens and Di Stefano, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2145},
  URN =		{urn:nbn:de:0030-drops-21450},
  doi =		{10.4230/OASIcs.ATMOS.2009.2145},
  annote =	{Keywords: Timetable information, flight modeling, shortest paths, multi criteria, table lookups Timetable information, flight modeling, shortest paths, multi criteria, table lookups}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2008.1582
Engineering Time-Expanded Graphs for Faster Timetable Information

Authors: Daniel Delling, Thomas Pajor, and Dorothea Wagner

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Abstract
We present an extension of the well-known time-expanded approach for timetable information. By remodeling unimportant stations, we are able to obtain faster query times with less space consumption than the original model. Moreover, we show that our extensions harmonize well with speed-up techniques whose adaption to timetable networks is more challenging than one might expect.
Cite as

Daniel Delling, Thomas Pajor, and Dorothea Wagner. Engineering Time-Expanded Graphs for Faster Timetable Information. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{delling_et_al:OASIcs.ATMOS.2008.1582,
  author =	{Delling, Daniel and Pajor, Thomas and Wagner, Dorothea},
  title =	{{Engineering Time-Expanded Graphs for Faster Timetable Information}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1582},
  URN =		{urn:nbn:de:0030-drops-15826},
  doi =		{10.4230/OASIcs.ATMOS.2008.1582},
  annote =	{Keywords: Timetable information, shortest path, modeling}
}
Document
DOI: 10.4230/DagSemProc.08191.4
08191 Working Group Report – Visualization of Trajectories

Authors: Stephen Borgatti, Ulrik Brandes, Michael Kaufmann, Stephen Kobourov, Anna Lubiw, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 8191, Graph Drawing with Applications to Bioinformatics and Social Sciences (2008)

Abstract
We considered the following problem: Given a set of vertices V and a set of paths P, where each path is a sequence of vertices, represent these paths somehow. We explored representations in different dimensions and with different conditions on the paths.
Cite as

Stephen Borgatti, Ulrik Brandes, Michael Kaufmann, Stephen Kobourov, Anna Lubiw, and Dorothea Wagner. 08191 Working Group Report – Visualization of Trajectories. In Graph Drawing with Applications to Bioinformatics and Social Sciences. Dagstuhl Seminar Proceedings, Volume 8191, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{borgatti_et_al:DagSemProc.08191.4,
  author =	{Borgatti, Stephen and Brandes, Ulrik and Kaufmann, Michael and Kobourov, Stephen and Lubiw, Anna and Wagner, Dorothea},
  title =	{{08191 Working Group Report – Visualization of Trajectories}},
  booktitle =	{Graph Drawing with Applications to Bioinformatics and Social Sciences},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8191},
  editor =	{Stephen P. Borgatti and Stephen Kobourov and Oliver Kohlbacher and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08191.4},
  URN =		{urn:nbn:de:0030-drops-15558},
  doi =		{10.4230/DagSemProc.08191.4},
  annote =	{Keywords: Graph drawing, trajectories, paths}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2007.1169
14. Experimental Study on Speed-Up Techniques for Timetable Information Systems

Authors: Reinhard Bauer, Daniel Delling, and Dorothea Wagner

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract
During the last years, impressive speed-up techniques for Dijkstra's algorithm have been developed. Unfortunately, recent research mainly focused on road networks. However, fast algorithms are also needed for other applications like timetable information systems. Even worse, the adaption of recently developed techniques to timetable information is often more complicated than expected. In this work, we check whether results from road networks are transferable to timetable information. To this end, we present an extensive experimental study of the most prominent speed-up techniques on different types of inputs. It turns out that recently developed techniques are much slower on graphs derived from timetable information than on road networks. In addition, we gain amazing insights into the behavior of speed-up techniques in general.
Cite as

Reinhard Bauer, Daniel Delling, and Dorothea Wagner. 14. Experimental Study on Speed-Up Techniques for Timetable Information Systems. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 209-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:OASIcs.ATMOS.2007.1169,
  author =	{Bauer, Reinhard and Delling, Daniel and Wagner, Dorothea},
  title =	{{14. Experimental Study on Speed-Up Techniques for Timetable Information Systems}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{209--225},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1169},
  URN =		{urn:nbn:de:0030-drops-11695},
  doi =		{10.4230/OASIcs.ATMOS.2007.1169},
  annote =	{Keywords: Speed-up techniques, timetable information, shortest path}
}
Document
DOI: 10.4230/DagSemProc.06091.1
06091 Abstracts Collection – Data Structures

Authors: Lars Arge, Robert Sedgewick, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)

Abstract
From 26.02.06 to 03.03.06, the Dagstuhl Seminar 06091 ``Data Structures'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Lars Arge, Robert Sedgewick, and Dorothea Wagner. 06091 Abstracts Collection – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.06091.1,
  author =	{Arge, Lars and Sedgewick, Robert and Wagner, Dorothea},
  title =	{{06091 Abstracts Collection – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.1},
  URN =		{urn:nbn:de:0030-drops-8428},
  doi =		{10.4230/DagSemProc.06091.1},
  annote =	{Keywords: Algorithms, data structures}
}
Document
DOI: 10.4230/DagSemProc.06091.2
06091 Executive Summary – Data Structures

Authors: Lars Arge, Robert Sedgewick, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)

Abstract
The Dagstuhl Seminar on Data Structures in 2006 reported on ongoing research on data structures, including randomized, cache-oblivious and succinct data structures. There was some shift of interest away from purely theoretical issues towards scientific studies that are directly relevant to practical applications. The participants were asked to think about the direction that research on data structure should take. Several presentations were provocative responses to this question. Interest in the topic remains high: another attendance record was set.
Cite as

Lars Arge, Robert Sedgewick, and Dorothea Wagner. 06091 Executive Summary – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.06091.2,
  author =	{Arge, Lars and Sedgewick, Robert and Wagner, Dorothea},
  title =	{{06091 Executive Summary – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.2},
  URN =		{urn:nbn:de:0030-drops-8411},
  doi =		{10.4230/DagSemProc.06091.2},
  annote =	{Keywords: algorithms, data structures}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2005.661
Station Location - Complexity and Approximation

Authors: Steffen Mecke, Anita Schöbel, and Dorothea Wagner

Published in: OASIcs, Volume 2, 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05) (2006)

Abstract
We consider a geometric set covering problem. In its original form it consists of adding stations to an existing geometric transportation network so that each of a given set of settlements is not too far from a station. The problem is known to be NP-hard in general. However, special cases with certain properties have been shown to be efficiently solvable in theory and in practice, especially if the covering matrix has (almost) consecutive ones property. In this paper we are narrowing the gap between intractable and efficiently solvable cases of the problem. We also present an approximation algorithm for cases with almost consecutive ones property.
Cite as

Steffen Mecke, Anita Schöbel, and Dorothea Wagner. Station Location - Complexity and Approximation. In 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05). Open Access Series in Informatics (OASIcs), Volume 2, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{mecke_et_al:OASIcs.ATMOS.2005.661,
  author =	{Mecke, Steffen and Sch\"{o}bel, Anita and Wagner, Dorothea},
  title =	{{Station Location - Complexity and Approximation}},
  booktitle =	{5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)},
  pages =	{1--11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-00-2},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{2},
  editor =	{Kroon, Leo G. and M\"{o}hring, Rolf H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2005.661},
  URN =		{urn:nbn:de:0030-drops-6612},
  doi =		{10.4230/OASIcs.ATMOS.2005.661},
  annote =	{Keywords: Station Location, facility location, complexity, approximation}
}
Document
DOI: 10.4230/DagSemProc.05361.1
05361 Abstracts Collection – Algorithmic Aspects of Large and Complex Networks

Authors: Stefano Leonardi, Friedhelm Meyer auf der Heide, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
From 04.09.05 to 09.09.05, the Dagstuhl Seminar 05361 ``Algorithmic Aspects of Large and Complex Networks'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Stefano Leonardi, Friedhelm Meyer auf der Heide, and Dorothea Wagner. 05361 Abstracts Collection – Algorithmic Aspects of Large and Complex Networks. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{leonardi_et_al:DagSemProc.05361.1,
  author =	{Leonardi, Stefano and Meyer auf der Heide, Friedhelm and Wagner, Dorothea},
  title =	{{05361 Abstracts Collection – Algorithmic Aspects of Large and Complex Networks}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.1},
  URN =		{urn:nbn:de:0030-drops-5702},
  doi =		{10.4230/DagSemProc.05361.1},
  annote =	{Keywords: Algorithms, Large and Complex Networks}
}
Document
DOI: 10.4230/DagSemProc.05361.3
A Hybrid Model for Drawing Dynamic and Evolving Graphs

Authors: Marco Gaertler and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
Dynamic processes frequently occur in many applications. Visualizations of dynamically evolving data, for example as part of the data analysis, are typically restricted to a cumulative static view or an animation/sequential view. Both methods have their benefits and are often complementary in their use. We present a hybrid model that combines the two techniques. This is accomplished by 2.5D drawings which are calculated in an incremental way. The method has been evaluated on collaboration networks.
Cite as

Marco Gaertler and Dorothea Wagner. A Hybrid Model for Drawing Dynamic and Evolving Graphs. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{gaertler_et_al:DagSemProc.05361.3,
  author =	{Gaertler, Marco and Wagner, Dorothea},
  title =	{{A Hybrid Model for Drawing Dynamic and Evolving Graphs}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.3},
  URN =		{urn:nbn:de:0030-drops-5683},
  doi =		{10.4230/DagSemProc.05361.3},
  annote =	{Keywords: Visualization dynamic/evolving graphs 2.5D}
}
Document
DOI: 10.4230/DagSemProc.04261.1
04261 Abstracts Collection – Algorithmic Methods for Railway Optimization

Authors: Leo G. Kroon, Dorothea Wagner, Frank Geraets, and Christos Zaroliagis

Published in: Dagstuhl Seminar Proceedings, Volume 4261, Algorithmic Methods for Railway Optimization (2006)

Abstract
From 20.06.04 to 25.06.04, the Dagstuhl Seminar 04261 ``Algorithmic Methods for Railway Optimization'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Leo G. Kroon, Dorothea Wagner, Frank Geraets, and Christos Zaroliagis. 04261 Abstracts Collection – Algorithmic Methods for Railway Optimization. In Algorithmic Methods for Railway Optimization. Dagstuhl Seminar Proceedings, Volume 4261, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{kroon_et_al:DagSemProc.04261.1,
  author =	{Kroon, Leo G. and Wagner, Dorothea and Geraets, Frank and Zaroliagis, Christos},
  title =	{{04261 Abstracts Collection – Algorithmic Methods for Railway Optimization}},
  booktitle =	{Algorithmic Methods for Railway Optimization},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{4261},
  editor =	{Leo G. Kroon and Frank Geraets and Dorothea Wagner and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04261.1},
  URN =		{urn:nbn:de:0030-drops-4712},
  doi =		{10.4230/DagSemProc.04261.1},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemProc.04091.1
04091 Abstracts Collection – Data Structures

Authors: Susanne Albers, Robert Sedgewick, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 4091, Data Structures (2005)

Abstract
From 22.02. to 27.02.2004, Dagstuhl Seminar "Data Structures" was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar are put together in this paper. The first section describes the seminar topics and goals in general.
Cite as

Susanne Albers, Robert Sedgewick, and Dorothea Wagner. 04091 Abstracts Collection – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 4091, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:DagSemProc.04091.1,
  author =	{Albers, Susanne and Sedgewick, Robert and Wagner, Dorothea},
  title =	{{04091 Abstracts Collection – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4091},
  editor =	{Susanne Albers and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04091.1},
  URN =		{urn:nbn:de:0030-drops-1758},
  doi =		{10.4230/DagSemProc.04091.1},
  annote =	{Keywords: Cache oblivious algorithms , cell probe model , computational geometry , data compression , dictionaries , finger search , hashing , heaps I/O efficiency , lower bounds}
}
Document
DOI: 10.4230/DagSemRep.391
Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 03361)

Authors: Micah Adler, Friedhelm Meyer auf der Heide, and Dorothea Wagner

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Micah Adler, Friedhelm Meyer auf der Heide, and Dorothea Wagner. Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 03361). Dagstuhl Seminar Report 391, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{adler_et_al:DagSemRep.391,
  author =	{Adler, Micah and Meyer auf der Heide, Friedhelm and Wagner, Dorothea},
  title =	{{Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 03361)}},
  pages =	{1--5},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{391},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.391},
  URN =		{urn:nbn:de:0030-drops-152711},
  doi =		{10.4230/DagSemRep.391},
}
Document
DOI: 10.4230/DagSemRep.314
Link Analysis and Visualization (Dagstuhl Seminar 01271)

Authors: Ulrik Brandes, David Krackhardt, Roberto Tamassia, and Dorothea Wagner

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Ulrik Brandes, David Krackhardt, Roberto Tamassia, and Dorothea Wagner. Link Analysis and Visualization (Dagstuhl Seminar 01271). Dagstuhl Seminar Report 314, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{brandes_et_al:DagSemRep.314,
  author =	{Brandes, Ulrik and Krackhardt, David and Tamassia, Roberto and Wagner, Dorothea},
  title =	{{Link Analysis and Visualization (Dagstuhl Seminar 01271)}},
  pages =	{1--16},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{314},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.314},
  URN =		{urn:nbn:de:0030-drops-151988},
  doi =		{10.4230/DagSemRep.314},
}
Document
DOI: 10.4230/DagSemRep.320
Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 01381)

Authors: Micah Adler, Friedhelm Meyer auf der Heide, and Dorothea Wagner

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Micah Adler, Friedhelm Meyer auf der Heide, and Dorothea Wagner. Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 01381). Dagstuhl Seminar Report 320, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2001)

Copy BibTex To Clipboard

@TechReport{adler_et_al:DagSemRep.320,
  author =	{Adler, Micah and Meyer auf der Heide, Friedhelm and Wagner, Dorothea},
  title =	{{Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 01381)}},
  pages =	{1--21},
  ISSN =	{1619-0203},
  year =	{2001},
  type = 	{Dagstuhl Seminar Report},
  number =	{320},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.320},
  URN =		{urn:nbn:de:0030-drops-152041},
  doi =		{10.4230/DagSemRep.320},
}
Document
DOI: 10.4230/DagSemRep.219
Graph Algorithms and Applications (Dagstuhl Seminar 98301)

Authors: Takao Nishizeki, Roberto Tamassia, and Dorothea Wagner

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Takao Nishizeki, Roberto Tamassia, and Dorothea Wagner. Graph Algorithms and Applications (Dagstuhl Seminar 98301). Dagstuhl Seminar Report 219, pp. 1-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1998)

Copy BibTex To Clipboard

@TechReport{nishizeki_et_al:DagSemRep.219,
  author =	{Nishizeki, Takao and Tamassia, Roberto and Wagner, Dorothea},
  title =	{{Graph Algorithms and Applications (Dagstuhl Seminar 98301)}},
  pages =	{1--38},
  ISSN =	{1619-0203},
  year =	{1998},
  type = 	{Dagstuhl Seminar Report},
  number =	{219},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.219},
  URN =		{urn:nbn:de:0030-drops-151058},
  doi =		{10.4230/DagSemRep.219},
}
Document
DOI: 10.4230/DagSemRep.145
Graph Algorithms and Applications (Dagstuhl Seminar 9620)

Authors: Takao Nishizeki, Roberto Tamassia, and Dorothea Wagner

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Takao Nishizeki, Roberto Tamassia, and Dorothea Wagner. Graph Algorithms and Applications (Dagstuhl Seminar 9620). Dagstuhl Seminar Report 145, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1996)

Copy BibTex To Clipboard

@TechReport{nishizeki_et_al:DagSemRep.145,
  author =	{Nishizeki, Takao and Tamassia, Roberto and Wagner, Dorothea},
  title =	{{Graph Algorithms and Applications (Dagstuhl Seminar 9620)}},
  pages =	{1--28},
  ISSN =	{1619-0203},
  year =	{1996},
  type = 	{Dagstuhl Seminar Report},
  number =	{145},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.145},
  URN =		{urn:nbn:de:0030-drops-150321},
  doi =		{10.4230/DagSemRep.145},
}
Document
DOI: 10.4230/DagSemRep.76
Combinatorial Methods for Integrated Circuits Design (Dagstuhl Seminar 9342)

Authors: Thomas Lengauer, Majid Sarrafzadeh, and Dorothea Wagner

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Thomas Lengauer, Majid Sarrafzadeh, and Dorothea Wagner. Combinatorial Methods for Integrated Circuits Design (Dagstuhl Seminar 9342). Dagstuhl Seminar Report 76, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1994)

Copy BibTex To Clipboard

@TechReport{lengauer_et_al:DagSemRep.76,
  author =	{Lengauer, Thomas and Sarrafzadeh, Majid and Wagner, Dorothea},
  title =	{{Combinatorial Methods for Integrated Circuits Design (Dagstuhl Seminar 9342)}},
  pages =	{1--20},
  ISSN =	{1619-0203},
  year =	{1994},
  type = 	{Dagstuhl Seminar Report},
  number =	{76},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.76},
  URN =		{urn:nbn:de:0030-drops-149646},
  doi =		{10.4230/DagSemRep.76},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact